package cn.itsource.recursion;

/**
 *	递归：
 *		1. 概念：是一种思想。在方法内部调用自己的方法。（自己干自己）
 *		2. 作用：就是简化逻辑（循环）代码。
 *		3. 核心规律：
 *				1. 通过数值带入的方式，查找逻辑规律：
 *						就是有相似运算逻辑的代码，就是通过已知条件表示未知条件
 *				2. 通过条件判断（条件/循环）的方式，在满足条件的时候根据规律调用自己的方法。如果不满足就不会自己的方法，这就是出口
 *	
 *		4. 注意事项：
 *			1. 递归必须 有出口
 *			2. 能用循环用循环，不要用递归，因为效率极其低下。
 *			为什么效率低下？
 *				方法的调用都是创建新栈帧，入栈，而栈层级是有限制的
 *			StackOverflowError : 栈内存溢出错误。
 *
 *		5. 使用场景：
 *			1. 树状结构数据或者菜单结构的数据查询
 *			2. 有相似逻辑运算的结构
 *			3. 适用于层级结构少，数据量小的场景。（最重要）如果层级多，且数据量大用循环。
 *
 *		6. 解决了哪些问题：
 *			1. 汉诺塔
 *			2. 斐波拉契数列
 *			...
 */
public class RecursionTest2 {

	public static void main(String[] args) {
		int fn = fn(-1);
		System.out.println(fn);
	}
	
	/**
	 * 
	 * 求n的斐波拉契数列
	 * 已知：
	 * 		核心规律：
 *				1. 通过数值带入的方式，查找逻辑规律：
 *						就是有相似运算逻辑的代码，就是通过已知条件表示未知条件（将所有的条件写出来）
 *				2. 通过条件判断（条件/循环）的方式，在满足条件的时候根据规律调用自己的方法。如果不满足就不会自己的方法，这就是出口
	 * 		fn(1) = 1
	 * 		fn(2) = 1
	 * 		fn(3) = 2 => fn(2) + fn(1)
	 * 		fn(4) = 3 => fn(3) + fn(2)
	 * 		fn(5) = 5 => fn(4) + fn(3)
	 */
	public static int fn(int n) {
		//将所有已知的条件写出来
		if(n < 1){
			return -1;//表示一种状态
		} else if (n == 1) {//已知的条件
			return 1;
		} else if (n == 2) {//已知的条件
			return 1;
		} else {//通过已知条件表示未知条件
			return fn(n-1) + fn(n-2);
		}
	}
	
}
